/**
 * @ClassName:
 * @author:
 * @Description:
 * @Date
 **/

public class BinarySearch3 {
    private BinarySearch3() {
    }

    //查找小于target的最大值
    public static <E extends Comparable<E>> int lower(E[] data, E target) {
        int l = -1, r = data.length - 1;
        while (l < r) {
            //避免计算机在整除时下取整导致lr相邻时区间大小不改变的问题
            int mid = l + (r - l + 1) / 2;
            if (data[mid].compareTo(target) < 0) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    //如果数组中存在target，返回最小索引
    //如果数组中不存在target，返回lower
    public static <E extends Comparable<E>> int lower_floor(E[] data, E target) {
        //小于target的最大值
        int lower = lower(data, target);
        //如果lower+1的位置正好等于target，那么最小索引就是这个位置
        if (lower + 1 < data.length && data[lower + 1].compareTo(target) == 0) {
            return lower + 1;
        }
        return lower;
    }

    //如果数组中存在target，返回最大索引
    //如果数组中不存在target，返回lower
    // <=target的最大值
    public static <E extends Comparable<E>> int upper_floor(E[] data, E target) {
        //小于target的最大值
        //这里的lower其实就是-1,因为如果lower比数组中任何元素都小的话，-1肯定就是那个最大的
        int l = -1, r = data.length - 1;
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (data[mid].compareTo(target) > 0) {
                r = mid - 1;
            } else {
                //当mid小于等于target时，mid本身也可能是答案
                l = mid;
            }
        }
        return l;
    }

    public static void main(String[] args) {
        Integer[] arr = {1, 1, 3, 3, 5, 5};
        for (int i = 0; i <= 6; i++) {
            System.out.print(lower(arr, i) + " ");
        }
    }
}
